Rendering complex geometric models at interactive rates is a challenging problem in computer graphics. While rendering performance is continually improving, significant gains can be obtained by adapting the complexity of a geometric model to the contribution the model makes to a specific rendered graphical image. Within traditional modeling systems known in the computer graphics art, detailed geometric models are created by applying versatile modeling operations (e.g., extrusion, constructive solid geometry, and freeform deformations) to a vast array of geometric primitives used to define a graphical object or image. The geometric primitives typically include triangles, polygons, and other mullet-sided shapes. For efficient display, the resulting geometric models are typically transformed into polygonal approximations of geometric primitives called "meshes."
A mesh has a geometry denoted by a tuple (K, V) where K is a simplicial complex specifying the connectivity of the mesh simplicies (i.e., the adjacency of the vertices, edges and faces), V={v.sub.1, . . . v.sub.m }, is the set of vertex positions defining the shape of the mesh in R.sup.3 space. That is, a parametric domain .vertline.K.vertline..OR right.R.sup.m is constructed by identifying a vertex K with a canonical basis vector of R.sup.m, and defining the mesh as an image .phi.v(.vertline.K.vertline.) where .phi.v: R.sup.m .fwdarw.R.sup.3 is a linear map. For more information on meshes, see Mesh Optimization, by Hugues Hoppe, T. DeRose, F. Duchamp, J. McDonald, and W. Stuetzle, ACM SIGGKAPH'93 Proceedings, pp. 19-26.
Many geometric models in computer graphics are represented using triangle meshes. Geometrically, a triangle mesh is a piecewise linear surface with multiple triangular faces joined together at their edges. One common technique for using meshes to display a graphical object or image is to create several versions of a geometric model at various levels Of Detail (LOD) using progressive meshes. Such LOD meshes can be computed automatically using various mesh simplification techniques known in the art.
A Progressive Mesh (PM) representation is also used to capture a continuous sequence of meshes optimized for view-independent LOD control. Progressive meshes allow for fast traversal of the mesh sequence at run-time. For more information see Progressive Meshes, by Hugues Hoppe, ACM SIGGRAPH'96 Proceedings, pp. 99-108. Sets or sequences of view-independent progressive LOD meshes are appropriate for many computer graphic applications. However, there are several problems associated with using view-independent progressive LOD meshes when rendering large-scale geometric models such as a graphical terrain or other graphical environments that may surround a viewer.
One problem is that a large number of individual polygons or faces of the geometric model may lie outside a viewer's chosen view frustum (i.e., a view plane), and thus do not contribute to graphical object or image when it is rendered. Even though the faces which lie outside the view frustum are eventually culled (i.e., discarded), processing resources are wasted during rendering of a graphical image or object because the same levels of detail that is applied within the view frustum arc also applied to faces outside the view frustum.
Another problem is the unnecessary rendering of faces oriented away from the viewer. Such faces are typically culled during rendering using a "backfacing" test However, this backfacing test again wastes significant processing resources during rendering.
Yet another problem is that within the view frustum some regions of the model may lie much closer to the viewer than others. Progressive LOD meshes fail to provide the appropriate level of detail over the entire geometric model to handle such regions.
Some of these problems can be addressed by representing a graphical scene hierarchically as a hierarchy of meshes. Parts of the scene can be adjusted independently for each mesh in the hierarchy. However, establishing such hierarchies on continuous surfaces of a graphical object or image presents additional challenging problems.
One problem associated with establishing culling hierarchies is that visual "cracks" may appear in the progressive LOD meshes. For example, if a mesh representing a graphical terrain is partitioned into blocks, and the blocks are rendered at different levels of detail, cracks may appear in the terrain as it is displayed. In addition, the progressive LOD mesh block boundaries are unlikely to correspond to natural features in the terrain surface, resulting in sub-optimal approximations. Similar problems also arise in adaptive tessellation of smooth parametric surfaces.
Specialized methods known to those skilled in the graphical arts have been developed to adaptively refine meshes for the cases of height fields for graphical terrains, and some parametric surfaces. However, these methods cannot be applied in a general manner to an arbitrary mesh.
As is known in the art, a mesh can be refined using a set of constraints on a set of mesh transformations and a set of fixed refinement criteria. For example, a progressive mesh representation can be refined with a set of mesh transformations including an edge collapse operation and a vertex split operation constrained by a set of vertices. The set of fixed refinement criteria includes placing all candidate edges for edge collapse into a priority queue where the priority of each transformation is an energy cost that is used to fit a small number of points from the initial mesh into a mesh in the progressive mesh representation. For more information, see the Progressive Meshes paper cited above.
Refining a progressive mesh representation with fixed set of refinement criteria presents a number of problems. The set of constraints used and the set of fixed refinement criteria used for progressive meshes are not adequate for adaptively refining a progressive mesh representation. During adaptive refinement, areas of a progressive mesh representation will be refined (e.g., an area pointed toward a viewer) while other areas of the same progressive mesh representation will be coarsened (e.g., an area pointed away from a viewer). The set of constrained mesh transformations and the set of fixed refinement criteria used for progressive meshes are also not adequate for adaptively refining an arbitrary progressive mesh representation.
In accordance with an illustrative embodiment of the present invention, the problems associated with progressive LOD meshes, culling hierarchies and adaptively refining progressive mesh representations are overcome. A method and system are described for adaptively refining an arbitrary progressive mesh according to changing view-dependent parameters. A general method for adaptively refining an arbitrary progressive mesh with a set of constrained mesh transformations using a set of selective refinement criteria is also presented.
The method for adaptively refining an arbitrary progressive mesh according to changing view-dependent parameters includes re-parameterizing a progressive mesh representation M.sup.R to create a re-parameterized progressive mesh representation M.sup.RE. The re-parameterizing includes the selection of new vertices, faces or edges from a sequence of N-data structure records associated with the progressive mesh M.sup.R representation. A vertex hierarchy is constructed on the re-parameterized progressive mesh representation M.sup.RE. The construction of the vertex hierarchy is done using a traversal of re-parameterized vertices. However, other construction techniques could also be used.
The vertex hierarchy forms a "forest" of tree structures in which the "root" nodes are the vertices of a progressive mesh representation (e.g., M.sup.R) and the "leaf nodes" are the vertices of a re-parameterized mesh representation (e.g., M.sup.RE). However, other types of vertex hierarchies could also be used. The establishment of the vertex hierarchy allows creation of refinement dependencies for vertices re-parameterized in the re-parameterized progressive mesh representation M.sup.RE.
Values for a set of selective refinement criteria are pre-computed to make the run-time evaluation of the set of selective refinement criteria faster. In an alternative embodiment of the present invention, the set of selective refine criteria is completed at run-time.
At run-time an indication is received that one or more view-dependent parameters have changed. The re-parameterized progressive mesh representation M.sup.RE is adaptively refined using the vertex hierarchy, the pre-computed selective refinement criteria, and run-time computed selective refinement criteria to create an adaptively refined mesh. Adaptively refining the parameterized progressive mesh representation M.sup.RE includes refining areas of M.sup.RE with a series of constrained transformations as well as coarsening other areas of M.sup.RE with a series of constrained transformations.
The system for an illustrative embodiment of the present invention includes a locator/constructor module for constructing an arbitrary progressive mesh representation; a pre-processing module for loading the progressive mesh representation into a memory of a computer system, re-parameterizing the progressive mesh representation and performing pre-processing on a set of selective refinement criteria; and a renderer module for receiving changes in view-dependent parameters, evaluating selective refinement criteria, adaptively refining a re-parameterized progressive mesh representation, and rendering active faces. However, the system can include more or fewer modules and can combine functionality of the modules into more or fewer modules.
The general method for adaptively refining an arbitrary progressive mesh with a set of constrained mesh transformations using a set of selective refinement criteria includes selecting an arbitrary progressive mesh representation. A set of mesh transformations, constraints on the set of mesh transformations, and a set of selective refinement criteria are selected. At run-time, the refinement of the progressive mesh representation is adjusted by adding geometric primitives to the progressive mesh representation using the constrained set of mesh transformations and the set of selective refinement criteria to create a first approximation of a selectively refined mesh. The selectively refined mesh is adaptively refined by navigating through the selectively refined mesh. Adaptive refinement allows areas of the selectively refined mesh to be further refined, while other areas of the same selectively refined mesh are coarsened. This method allows an arbitrary progressive mesh representation for an arbitrary geometric model to be adaptively refined. The method is also very flexible as a developer can choose the set of selective refinement criteria. The selective refinement criteria can be view-dependent, or based on some other set of dependencies providing flexibility to adaptively refine a progressive mesh representation for a large number of purposes.